/*
 * @(#)IntegerFactoringPollardRho.java                  0.1 2011-11-09
 *
 * Copyright (c) 2011 David Falk, Klaus Nicosia, Marcus Oberg.
 */

import java.math.BigInteger;
import java.util.Random;

/**
 * Implementation of Pollard-Rho.
 *
 * @author      David Falk
 * @author      Klaus Nicosia
 * @author      Marcus Oberg.
 */
public class IntegerFactoringPollardRho {

	/** The BigInteger constant zero. */
	private static final BigInteger ZERO = BigInteger.ZERO;

	/** The BigInteger constant one. */
	private static final BigInteger ONE = BigInteger.ONE;

	/** The BigInteger constant two. */
	private static final BigInteger TWO = new BigInteger("2");

	/** The BigInteger constant three. */
	private static final BigInteger THREE = new BigInteger("3");

	/** The BigInteger constant five. */
	private static final BigInteger FIVE = new BigInteger("5");

	/** The BigInteger constant seven. */
	private static final BigInteger SEVEN = new BigInteger("7");

	/** The BigInteger constant seven. */
	private static final BigInteger ELEVEN = new BigInteger("7");

	/** The BigInteger constant seven. */
	private static final BigInteger THIRTEEN = new BigInteger("7");

	/** The BigInteger constant seven. */
	private static final BigInteger SEVENTEEN = new BigInteger("7");

	/** The BigInteger constant minus one. */
	private static final BigInteger MINUS_ONE = new BigInteger("-1");

	private static final BigInteger BRENT_LIMIT_HELP = new BigInteger("328000");

	/**
	 * Pollard-Rho algorithm with Brent's optimization (multiplications
	 * instead of GCD's) and with Brent's cycle detection.
	 *
	 * @param       n       the number to factor.
	 * @return              a factor of n or -1 if failure.
	 */
	public BigInteger pollardBrent(BigInteger n) {
		if (!n.testBit(0)) {
			return TWO;
		} else if (n.mod(THREE).compareTo(ZERO) == 0) {
			return THREE;
		} else if (n.mod(FIVE).compareTo(ZERO) == 0) {
			return FIVE;
		} else if (n.mod(SEVEN).compareTo(ZERO) == 0) {
			return SEVEN;
		} else if (n.mod(ELEVEN).compareTo(ZERO) == 0) {
			return ELEVEN;
		} else if (n.mod(THIRTEEN).compareTo(ZERO) == 0) {
			return THIRTEEN;
		} else if (n.mod(SEVENTEEN).compareTo(ZERO) == 0) {
			return SEVENTEEN;
		}

		int r = 1;      // Index for the second sequence.
		int m = n.bitLength(); // Number of multiplications before a GCD.
		int brentLimit = getBrentLimit(n);
		BigInteger x = MINUS_ONE;
		BigInteger y = generateRandom(n); // Get random starting value for y.
		BigInteger q = ONE;     // min(m, r - k) products of |x - y|.
		BigInteger g = ONE;     // GCD(q, n)
		BigInteger ys = y;      // Used for ordinary Pollard-Rho if Brent fails.

		while (g.compareTo(ONE) == 0) {
			x = y;
			for (int i = 0; i < r; i++) {
				y = y.multiply(y).subtract(ONE).mod(n);
			}
			int k = 0;
			while (k < r && g.compareTo(ONE) == 0) {
				ys = y;
				for (int i = 0; i < Math.min(m, r - k); i++) {
					y = y.multiply(y).subtract(ONE).mod(n);
					q = q.multiply(x.subtract(y)).mod(n);
				}
				g = q.gcd(n);
				k = k + m;
				IntegerFactoring.setTime(System.nanoTime());
				if (IntegerFactoring.getTime() - IntegerFactoring.getStartTime()
						> IntegerFactoring.getTimeLimit()) {
					return MINUS_ONE;
				}
				if (k > brentLimit) {
					return MINUS_ONE;
				}
			}
			r = 2 * r;
		}
		if (g.compareTo(n) == 0) {
			int i = 0;
			int pollardLimit = getPollardLimit(n);

			do  {
				ys = ys.multiply(ys).subtract(ONE).mod(n);
				g = x.subtract(ys).gcd(n);
				i++;
			} while (g.compareTo(ONE) == 0 && i < pollardLimit);
		}
		if (g.compareTo(n) == 0) {
			return MINUS_ONE;
		} else {
			return g;
		}
	}

	/**
	 * Randomly generates a BigInteger, distributed over the range 0 to
	 * (n - 1).
	 *
	 * @param       n       n - 1 is the maximum of the range.
	 * @return              the randomly generated BigInteger.
	 */
	private BigInteger generateRandom(BigInteger n) {
		Random random = new Random();
		BigInteger randomBigInteger =
			new BigInteger(n.bitLength(), random).mod(n);

		// Repeat if the generated value is larger than or equal to n.
		while (randomBigInteger.compareTo(n) >= 0) {
			randomBigInteger = new BigInteger(n.bitLength(), random).mod(n);
		}
		return randomBigInteger;
	}

	/**
	 * Returns a limit for the Brent part of the algorithm (multiplications are
	 * done instead of GCD's). The values were found empirically for the
	 * problem.
	 *
	 * @param       n       the number for which the limit is returned.
	 * @return              the limit.
	 */
	private int getBrentLimit(BigInteger n) {
		if (n.compareTo(BRENT_LIMIT_HELP) < 0) {
			return n.intValue() / 10;
		}
		return BRENT_LIMIT_HELP.intValue() / 10;
	}

	/**
	 * Returns a limit for the Pollard-Rho part of the algorithm (were GCD is
	 * done in each iteration). The values were found empirically for the
	 * problem.
	 *
	 * @param       n       the number for which the limit is returned.
	 * @return              the limit.
	 */
	private int getPollardLimit(BigInteger n) {
		if (n.compareTo(BigInteger.TEN) < 0) {
			return n.intValue();
		} else if (n.compareTo(new BigInteger("100")) < 0) {
			return n.intValue() / 2;
		}
		return 100;
	}

	/**
	 * Pollard-Rho algorithm without Brent's optimization (multiplications
	 * instead of GCD's) but with Brent's cycle detection.
	 *
	 * @param       n       the number to factor.
	 * @return              a factor of n or -1 if failure.
	 */
	public BigInteger pollardRho(BigInteger n) {
		if (!n.testBit(0)) {
			return TWO;
		} else if (n.mod(THREE).compareTo(ZERO) == 0) {
			return THREE;
		} else if (n.mod(FIVE).compareTo(ZERO) == 0) {
			return FIVE;
		} else if (n.mod(SEVEN).compareTo(ZERO) == 0) {
			return SEVEN;
		}

		int i = 1;
		int k = 2;
		int limit = getPollardLimit(n);
		BigInteger x = generateRandom(n); // Get random starting value for x.
		BigInteger y = x;
		BigInteger d;

		while (i <= limit) {
			i++;
			x = x.multiply(x).subtract(ONE).mod(n);
			d = n.gcd(y.subtract(x));

			if (d.compareTo(ONE) != 0 && d.compareTo(n) != 0) {
				return d;
			}

			if (i == k) {
				y = x;
				k = 2 * k;
			}
		}
		return MINUS_ONE;
	}
}